package com.wx.datastructure.linked;

import java.util.Objects;

/**
 * @author wx
 * @Description:
 * @date 2018/12/17 001722:08
 */
public class BothwayLinkedList<E> implements ILinked<E> {

    private Node node;
    private int size;

    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.node == null || this.size == 0;
    }

    @Override
    public void addFirst(E e) {
        add(0, e);
    }

    @Override
    public void addLast(E e) {
        add(size - 1, e);
    }

    @Override
    public void add(int index, E e) {
        validationAddIndex(index);
        if (index == 0) {
            Node lastNode = getLastNode();
            Node originalNode = this.node;
            this.node = new Node(e);
            this.node.previous = originalNode == null ? this.node : lastNode;
            this.node.next = lastNode == null ? this.node : originalNode;
            if (lastNode != null && originalNode != null) {
                originalNode.previous = this.node;
                lastNode.next = this.node;
            }
        } else {
            Node nodeHead = this.node;
            for (int i = 1; i <= index; i++) {
                nodeHead = nodeHead.next;
            }
            Node next = nodeHead.next;
            if (next == null) {
                nodeHead.next = new Node(e, this.node, nodeHead);
                this.node.previous = nodeHead.next;
            } else {
                nodeHead.next = new Node(e, next, nodeHead);
                next.previous = nodeHead.next;
            }
        }
        this.size++;
    }

    @Override
    public E getFirst() {
        return get(0);
    }

    @Override
    public E getLast() {
        return getLastNode() == null ? null : getLastNode().e;
    }

    @Override
    public E get(int index) {
        return this.node.e;
    }

    @Override
    public E removeFirst() {
        Node lastNode = this.node.previous;
        Node oldNode = this.node;
        this.node = this.node.next;
        this.node.previous = lastNode;
        lastNode.next = this.node;
        //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
        oldNode.next = null;
        oldNode.previous = null;
        this.size --;
        return oldNode.e;
    }

    @Override
    public E removeLast() {
        Node lastNode = this.node.previous;
        Node prevNode = lastNode.previous;
        this.node.previous = prevNode;
        prevNode.next = this.node;
        //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
        lastNode.next = null;
        lastNode.previous = null;
        this.size --;
        return lastNode.e;
    }

    @Override
    public void removeElement(E e) {
        Node prev = this.node;
        for (int i = 0; i <= this.size; i++){
            if(Objects.equals(prev.e,e)) {
                break;
            }
            if (i == this.size){
                prev = null;
                return;
            }
            prev = prev.next;
        }

        if(prev != null){
            Node delNode = prev.next;
            if (delNode == null){
                prev.previous.next = this.node;
                this.node.previous = prev.previous;
                //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
                prev.previous = null;
            } else {
                prev.previous.next = delNode;
                delNode.previous = prev.previous;
                //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
                prev.previous = null;
                prev.next = null;
            }
            size --;
        }
    }

    @Override
    public void set(int index, E e) {
        Node element = getByIndexNode(index);
        element.e = e;
    }

    @Override
    public boolean contains(E e) {
        return getNodeByContent(e,this.node) != null;
    }


    /**
     * @param index
     * @description: 验证下标是否合法
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: void
     */
    private void validationIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index 不合法,index < 0 and index >= size");
        }
    }


    /**
     * @param index
     * @description: 验证下标是否合法
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: void
     */
    private void validationAddIndex(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index 不合法,index < 0 and index >= size");
        }
    }

    /**
     * @param index
     * @description: 根据下标获取node节点
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: com.wx.datastructure.linked.LinkedList<E>.Node
     */
    private Node getByIndexNode(int index) {
        validationIndex(index);
        Node element = this.node;
        for (int i = 1; i <= index; i++) {
            element = element.next;
        }
        return element;
    }


    /**
     * @param index
     * @description: 根据下标删除
     * @author: wx
     * @date: 2018/12/17 0017
     * @return: E
     */
    private E remove(int index) {
        validationIndex(index);
        if (index == 0) {
            Node firstNode = this.node;
            Node lastNode = getLastNode();
            //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
            this.node = this.node.next;
            this.node.previous = lastNode;
            lastNode.next = this.node;
            firstNode.next = null;
            firstNode.previous = null;
            this.size--;
            return firstNode.e;
        } else {
            Node element = this.node;
            for (int i = 1; i <= index; i++) {
                element = element.next;
            }
            Node retNode = element.next;
            element.next = retNode.next;
            element.next.previous = element;
            //如果被删除节点内部引用类型没有被清除，那么这个对象无法被垃圾回收
            retNode.next = null;
            retNode.previous = null;
            this.size--;
            return element.e;
        }
    }

    /**
     * @param e
     * @description: 根据内容递归查询返回node节点
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: com.wx.datastructure.linked.BothwayLinkedList<E>.Node
     */
    private Node getNodeByContent(E e, Node element) {
        for (int i = 0; i < this.size; i++){
            if (Objects.equals(e, element.e)) {
                return element;
            }
            element = element.next;
        }
        return  null;
    }


    /**
     * @description: 递归获取最后一个节点
     * @author: wx
     * @date: 2018/12/15 0015
     * @return: com.wx.datastructure.linked.BothwayLinkedList<E>.Node
     */
    private Node getLastNode() {
        return this.node == null ? null : this.node.previous;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        Node prev = this.node;
        int i = 0;
        while (i <= this.size){
            res.append(prev.e).append("->");
            prev = prev.next;
            i++;
        }
        return res.toString();
    }

    /**
     * @author wx
     * @Description: 节点对象
     * @date 2018-12-15
     */
    private class Node {
        public E e;
        /**
         * 上一个节点
         */
        public Node previous;
        /**
         * 下个节点
         */
        public Node next;

        public Node(E e, Node next, Node previous) {
            this.e = e;
            this.next = next;
            this.previous = previous;
        }

        public Node(E e, Node next) {
            this(e, next, null);
        }

        public Node(E e) {
            this(e, null, null);
        }

        public Node() {
            this(null, null, null);
        }

    }
}
